package com.utils;

import java.io.IOException;

public class MyALVTree {

    //内部类
    private static class AVLNode{
        /** 数据 **/
        public Map data;
        /** 相对高度 **/
        public int height;
        /** 平衡因子**/
        int bf;
        /** 父节点 **/
        public AVLNode parent;
        /** 左子树 **/
        public AVLNode left;
        /** 右子树 **/
        public AVLNode right;
        public AVLNode(Map data) {
            this.data = data;
            this.height = 1;
        }
    }

    public AVLNode root;
    final int LH =+1;                        /*  左高 */
    final int EH= 0;                            /*  等高 */
    final int RH=-1;                           /*  右高 */
    final int LC=0;                         //在左子树插入
    final int RC=1;							//在右子树插入

    /**
     * 计算 BF
     * BF（平衡因子）的值为：左子树高度 - 右子树高度
     * @param root
     * @return
     */
    private int calcBF(AVLNode root) {
        if (root == null){
            return 0;
        }
        else if (root.left == null && root.right == null) {
            return 0;
        }
        else if (root.right == null) {
            return root.left.height ;
        } else if (root.left == null) {
            return - root.right.height;
        }else {
            return root.left.height - root.right.height;
        }
    }

    public void insert(Map data) {
        if (null == this.root) {
            this.root = new AVLNode(data);
            return;
        }
        this.root = insert(this.root, data);
    }
    public AVLNode insert(AVLNode root, Map data) {
        //插入左子树
        if (data.getLinkID() < root.data.getLinkID()) {
            if (null == root.left) {
                root.left = new AVLNode(data);
                root.left.parent = root;
            }else {
                insert(root.left,data);
            }
        }
        //插入右子树
        else if (data.getLinkID() > root.data.getLinkID()) {
            if (null == root.right) {
                root.right = new AVLNode(data);
                root.right.parent = root;
            } else {
                insert(root.right,data);
            }
        }
        //刷新高度
        root.height = calcHeight(root);
        //旋转
        //1. LL 型 右旋转
        if (calcBF(root) == 2){
            //2. LR 型 先左旋转
            if (calcBF(root.left) == -1) {
                root.left = leftRotate(root.left);
            }
            root = rightRotate(root);
        }
        //3. RR型 左旋转
        if (calcBF(root) == -2){
            //4. RL 型 先右旋转
            if (calcBF(root.right)== 1) {
                root.right = rightRotate(root.right);
            }
            root = leftRotate(root);
        }

        return root;
    }

    /**
     * 左旋
     * 旧根节点为新根节点的左子树
     * 新根节点的左子树（如果存在）为旧根节点的右子树
     * @param root
     * @return
     */
    public AVLNode leftRotate(AVLNode root) {
        AVLNode oldRoot = root;
        AVLNode newRoot = root.right;
        AVLNode parent = root.parent;
        //1.newRoot 替换 oldRoot 位置
        if (null != parent ) {
            if (oldRoot.parent.data.getLinkID() > oldRoot.data.getLinkID()) {
                parent.left = newRoot;
            }else  {
                parent.right = newRoot;
            }
        }
        newRoot.parent = parent;
        //2.重新组装 oldRoot (将 newRoot 的左子树 给 oldRoot 的右子树)
        oldRoot.right = newRoot.left;
        if (newRoot.left != null) {
            newRoot.left.parent = oldRoot;
        }
        //3. oldRoot 为 newRoot 的左子树
        newRoot.left = oldRoot;
        oldRoot.parent = newRoot;
        //刷新高度
        oldRoot.height = calcHeight(oldRoot);
        newRoot.height = calcHeight(newRoot);
        return newRoot;
    }


    /**
     * 右旋：
     * 旧根节点为新根节点的右子树
     * 新根节点的右子树（如果存在）为旧根节点的左子树
     * @param root
     * @return
     */
    public AVLNode rightRotate(AVLNode root) {
        AVLNode oldRoot = root;
        AVLNode newRoot = root.left;
        AVLNode parent = root.parent;
        //1.newRoot 替换 oldRoot 位置
        if (null != parent ) {
            if (oldRoot.parent.data.getLinkID() > oldRoot.data.getLinkID()) {
                parent.left = newRoot;
            }else {
                parent.right = newRoot;
            }
        }
        newRoot.parent = parent;
        //2.重新组装 oldRoot (将 newRoot 的右子树 给 oldRoot 的左子树)
        oldRoot.left = newRoot.right;
        if (newRoot.right != null) {
            newRoot.right.parent = oldRoot;
        }
        //3. oldRoot 为 newRoot 的左子树
        newRoot.right = oldRoot;
        oldRoot.parent = newRoot;
        //刷新高度
        oldRoot.height = calcHeight(oldRoot);
        newRoot.height = calcHeight(newRoot);
        return newRoot;
    }
    /** 通过子树高度 计算高度 **/
    private int calcHeight(AVLNode root) {
        if (root.left == null && root.right == null) {
            return 1;
        }
        else if (root.right == null) {
            return root.left.height + 1;
        } else if (root.left == null) {
            return root.right.height + 1;
        }else {
            return root.left.height > root.right.height ? root.left.height + 1 : root.right.height + 1;
        }
    }




    /**
     * 平衡二叉树遍历输出
     * @param root
     */
    public void innerTraverse(AVLNode root) {
        if (root == null) {
            return;
        }
        innerTraverse(root.left);
        System.out.println(root.data.toString() );
        innerTraverse(root.right);
    }


    static Map findMap;

    /**
     * 根据linkID查询数内数据
     * @param root
     * @param linkID
     * @return
     */
    public Map findMapByLinkID(AVLNode root,int linkID){

        if (root == null) {
            return findMap;
        }
        if ( linkID > root.data.getLinkID()){
            findMapByLinkID(root.right,linkID);
        }else if ( linkID < root.data.getLinkID() ){
            findMapByLinkID(root.left,linkID);
        }else {
            findMap = root.data;
            return findMap;
        }
        return findMap;
    }

    public void updateTreeByLinkID(AVLNode root,int linkID,Map updateMap){
        if (root == null)
            return;
        if (linkID > root.data.getLinkID()){
            updateTreeByLinkID(root.right,linkID,updateMap);
        }else if (linkID < root.data.getLinkID()){
            updateTreeByLinkID(root.left,linkID,updateMap);
        }else {
            root.data = updateMap;
            return;
        }
        return;
    }


    class TS {
        public boolean taller = false;
        public boolean shorter = false;
    }


    /**
     * 删除树结点入口方法
     * @param linkID
     * @return
     */
    public boolean deleteAVL(int linkID){
        if(root==null)
            throw new RuntimeException("这是空树！");
        TS ts=new TS();
        return deleteAVL(root,linkID,ts);
    }


    /*
    若在平衡的二叉排序树t中存在和e有相同关键字的结点，则删除之
    并返回TRUE，否则返回FALSE。若因删除而使二叉排序树
    失去平衡，则作平衡旋转处理，布尔变量shorter反映t变矮与否
    */


        private boolean deleteAVL(AVLNode root, int linkID, TS ts) {
            if (root == null)                                      //不存在该元素
            {
                return false;                                   //删除失败
            } else if (linkID == root.data.getLinkID())                           //找到元素结点
            {
                AVLNode q = null;
                if (root.left == null)                     //左子树为空
                {
                    q = root.parent;
                    if (q == null)
                        root = root.right;
                    else {
                        if (linkID < q.data.getLinkID())
                            q.left = root.right;
                        else
                            q.right = root.right;
                    }
                    ts.shorter = true;
                } else if (root.right == null)                    //右子树为空
                {
                    q = root.parent;
                    if (q == null)
                        root = root.left;
                    else {
                        if (linkID < q.data.getLinkID())
                            q.left = root.left;
                        else
                            q.right = root.left;
                    }
                    ts.shorter = true;
                } else                                            //左右子树都存在,
                {
                    q = root.left;
                    while (q.right != null) {
                        q = q.right;
                    }
                    root.data = q.data;
                    deleteAVL(root.left, q.data.getLinkID(), ts);   //在左子树中递归删除前驱结点
                }
            } else if (linkID < root.data.getLinkID())                         //左子树中继续查找
            {
                if (!deleteAVL(root.left, linkID, ts)) {
                    return false;
                }
                if (ts.shorter) {
                    switch (root.bf) {
                        case LH:
                            root.bf = EH;
                            ts.shorter = true;
                            break;
                        case EH:
                            root.bf = RH;
                            ts.shorter = false;
                            break;
                        case RH:
                            if (root.right.bf == EH)    //注意这里，画图思考一下
                                ts.shorter = false;
                            else
                                ts.shorter = true;
                            RightBalance(root);        //右平衡处理
                            break;
                    }
                }
            } else                                //右子树中继续查找
            {
                if (!deleteAVL(root.right, linkID, ts)) {
                    return false;
                }
                if (ts.shorter) {
                    switch (root.bf) {
                        case LH:
                            if (root.left.bf == EH)  //注意这里，画图思考一下
                                ts.shorter = false;
                            else
                                ts.shorter = true;
                            LeftBalance(root);         //左平衡处理
                            break;
                        case EH:
                            root.bf = LH;
                            ts.shorter = false;
                            break;
                        case RH:
                            root.bf = EH;
                            ts.shorter = true;
                            break;
                    }
                }
            }
            return true;
        }

        /*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
        /*  本算法结束时，指针T指向新的根结点 */
        public void LeftBalance(AVLNode T) {
            AVLNode L, Lr;
            L = T.left;                    /*  L指向T的左子树根结点 */
            switch (L.bf) {
                /* 检查T的左子树的平衡度，并作相应平衡处理 */
                case LH:                        /* 新结点插入在T的左孩子的左子树上，要作单右旋处理 */
                    T.bf = L.bf = EH;
                    rightRotate(T);
                    break;
                case RH:                        /* 新结点插入在T的左孩子的右子树上，要作双旋处理 */ //
                    Lr = L.right;                /* Lr指向T的左孩子的右子树根 */
                    switch (Lr.bf) {
                        /* 修改T及其左孩子的平衡因子 */
                        case LH:
                            T.bf = RH;
                            L.bf = EH;
                            break;
                        case EH:
                            T.bf = L.bf = EH;
                            break;
                        case RH:
                            T.bf = EH;
                            L.bf = LH;
                            break;
                    }
                    Lr.bf = EH;
                    leftRotate(T.left); /* 对T的左子树作左旋平衡处理 */
                    rightRotate(T);                /* 对T作右旋平衡处理 */
                    break;
                case EH:      //特殊情况4,这种情况在添加时不可能出现，只在移除时可能出现，旋转之后整体树高不变
                    L.bf = RH;
                    T.bf = LH;
                    rightRotate(T);
                    break;
            }
        }

        /*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */
        /*  本算法结束时，指针T指向新的根结点 */
        public void RightBalance(AVLNode T) {
            AVLNode R, Rl;
            R = T.right;                      /*  R指向T的右子树根结点 */
            switch (R.bf) {
                /*  检查T的右子树的平衡度，并作相应平衡处理 */
                case RH:                        /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */
                    T.bf = R.bf = EH;
                    leftRotate(T);
                    break;
                case LH:                        /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */ //最小不平衡树的根结点为负，其右孩子为正
                    Rl = R.left;                /*  Rl指向T的右孩子的左子树根 */
                    switch (Rl.bf) {
                        /*  修改T及其右孩子的平衡因子 */
                        case RH:
                            T.bf = LH;
                            R.bf = EH;
                            break;
                        case EH:
                            T.bf = R.bf = EH;
                            break;
                        case LH:
                            T.bf = EH;
                            R.bf = RH;
                            break;
                    }
                    Rl.bf = EH;
                    rightRotate(T.right); /*  对T的右子树作右旋平衡处理 */
                    leftRotate(T);                /*  对T作左旋平衡处理 */
                    break;
                case EH:      //特殊情况4,这种情况在添加时不可能出现，只在移除时可能出现，旋转之后整体树高不变
                    R.bf = LH;
                    T.bf = RH;
                    leftRotate(T);
                    break;

            }
        }


    }

//    // 递归先序遍历
//    private static void printTree(AVLNode t) {
//    //    System.out.println("先序遍历");
//        if (t != null) {
//            System.out.println(t.data + " ");
//            printTree(t.left);
//            printTree(t.right);
//        }
//    }
//
//    // 递归中序遍历 private void
//    private static void printTree1(AVLNode t) {
//    //    System.out.println("中序遍历");
//        if (t != null) {
//            printTree(t.left);
//            System.out.println(t.data + " ");
//            printTree(t.right);
//        }
//    }
//
//    // 递归后序遍历
//    private static void printTree3(AVLNode t ) {
//     //   System.out.println("后序遍历");
//        if (t != null) {
//            printTree(t.left);
//            printTree(t.right);
//            System.out.println(t.data + " ");
//        }
//    }



